package _0_4_买卖股票

/**
原题链接:
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

714. 买卖股票的最佳时机含手续费
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例 1：
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

示例 2：
输入：prices = [1,3,7,5,10,3], fee = 3
输出：6

思路:
dp数组含义:
	dp[i][0]: 第i天持有股票的现金数
	dp[i][1]: 第i天不持有股票的现金数

如果第i天持有股票即dp[i][0], 那么可以由两个状态推出来
	* 第i-1天就持有股票, 那么就保持现状, 现金为 : dp[i-1][0]
	* 第i天买入股票, 现金为: 昨天不持有股票现金 - 今天的股票价格
	可得: dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i])
如果第i天不持有股票即dp[i][1]的情况, 依然可以由两个状态推出来
	* 第i-1就不持有股票, 现金为: dp[i-1][1]
	* 第i天卖出的股票, 按照今天的股票价格进行卖出, 注意,这里需要有手续费了, 即: dp[i-1][0]+prices[i]-fee
	可得: dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]-fee)

本题和买卖股票最佳时机Ⅱ只多了一个减去手续费的操作
*/
// 买卖股票的最佳时机含手续费 动态规划
// 时间复杂度O(n) 空间复杂度O(n)
// 买卖股票的最佳时机含手续费 动态规划
// 时间复杂度O(n) 空间复杂度O(n)
func maxProfit714(prices []int, fee int) int {

	n := len(prices)
	dp := make([][2]int, n)
	dp[0][0] = -prices[0]

	for i := 1; i < n; i++ {
		dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i])
		dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]-fee)
	}

	return dp[n-1][1]
}
